
\documentclass[11pt]{article}
\newtheorem{define}{Definition}
%\newcommand{\F}{{\mathbb{F}}}
%\usepackage{psfig}
\usepackage{amsmath,amssymb,amsfonts}
\usepackage{fullpage, color}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}
\newcommand{\eps}{\epsilon}

%{lecture number}{lecture date}{Elena Grigorescu}{Your name}
\lecture{11}{Sep 25, 2012}{Elena Grigorescu}{Vaishnavi Chandrasekaran}


%%%% body goes in here %%%%

\section{Introduction}

There are many notions of expansion and in previous lectures we have seen  edge and spectrum expansion.  In this lecture, we will see the notion of vertex expansion. Many of these notions of expansion are in fact equivalent, but we won't discuss in this course why. 
Our goal today is to show that expanders exist using the probabilistic method. According to the probabilistic method, in order to show that some combinatorial object exists, we show that it does not exist with probability strictly less than 1.  This method is used to show existence many combinatorial objects, such as expanders, error-correcting codes, etc.

\section{A simple application of the probabilistic method}


\begin{definition}
Let $V$ be a set of $n$ vertices. A ``h-uniform hypergraph" is a graph on $V$ whose edge set is $E \subset 2^{[V]}$
and  where each edge has  $h$ vertices.  (So, a $2$-uniform hypergraph is a just a graph.)
\end{definition}


A {\em coloring} is defined as the assignment of colors red, blue to the vertices of the graph. An edge with only one color is said to be  {\em monochromatic}.
A graph is said to have {\em good coloring} if the coloring of the vertices are such that no monochromatic edge exists in the graph.

\begin{theorem}
Every $h$-uniform hypergraph with $<2^{(h-1)}$ edges has a good coloring.
\end{theorem}

\begin{proof}
We will use the probabilistic method. We'll show that a good coloring exists by counting the number of possible bad colorings.Assign a uniform random color (red/blue) to each vertex of the graph. Let us fix the edge $E_i$ (recall that it has $h$ vertices colored either red or blue.)
$\Pr_{colorings}[E_i \text{ is monochromatic}] = \Pr_{colorings}[\text{ All vertices in }E_i \text{ are  blue}]+ \Pr [\text{ All vertices in }E_i \text{ are red}]= \frac{1}{2^h} + \frac{1}{2^h} = \frac{1}{2^(h-1)}.$
By a union bound  over all edges of the hypergraph $\Pr[\exists \text{ some monochromatic edge }] < \frac{2^{(h-1)}}{2^{(h-1)}} = 1$. So there must exist a coloring with no monochromatic edge.
\end{proof}

\section{Expanders}

\begin{definition}
Let $G = (V,E)$ be a graph. The neighborhood of a vertex $v$ in  $G$ is the set of vertices adjacent to $v$. For a subset of vertices $S \subset V$, we define the \emph{neighbourhood of $S$} as: $N(S) = \{u \in V | \exists  u' \in S \text{ s.t. }(u, u')\in E.\}$ So $deg(v) = |N(v)|$
 
\end{definition}


\begin{definition}
A graph is said to be \emph{regular} of degree \emph{$d$} if each vertex has degree $d$. (A $0$-regular graph is an empty graph, a $1$-regular graph consists of disconnected edges, and a $2$-regular graph consists of disconnected cycles.) A bipartite graph $G = (L \cup R)$ is \emph{$d$-left regular} if every vertex on the left has a degree $d$. Similarly, $G$ is \emph{$(d, c)$-regular} if every vertex on the left has degree $d$ and every vertex on the right has degree $c$.
\end{definition}

\begin{definition}
A graph $G$ is a \emph{($K$,$\gamma$)-vertex expander} if for all sets $S$ of at most $K$ vertices $|N(S)| \geq \gamma \cdot |S|$. A {\em bipartite expander} $G=(L \cup R,E)$ is a $(K, \gamma)$-vertex expander if for all sets $S\subset L$ with $|S|\leq K$, $|N(S)|\geq \gamma |S|.$
\end{definition}

\subsection {Basic Properties of Expanders}
The maximum distance between any $2$ vertices (i.e. the diameter) of an expander graph is small, i.e. in the order of $\log n$.

\begin{lemma}
A $(\frac{n}{2}, \gamma)$ $d$-regular expander has  diameter $\leq 2log(\frac{n}{2d})$
\end{lemma}
\begin{proof}
Let $a, b \in V$.  Run a Breadth First Search (BFS) from each of the two vertices counting how many vertices we cover in $k$-steps. Since at step 1 we have $|N(a)|=d<n/2$ it follows that in 2 steps we cover at least $\gamma d$ vertices (by the expansion property), and inductively, at step $k$ from $a$ we cover a set  $|S(a)|=\gamma^k d$ vertices. Choose $k$ such that $\gamma^k d> n/2$ and so $k\leq \log n/2d.$ If $b\notin S(a)$ then running the same search from $b$, in $k$ steps we must have reached a vertex in $S(a)$. So there must exist a path from $a$ to $b$ of length  $2\log(\frac{n}{2d}).$
 
\end{proof}

\subsection{Existence of expanders}
What parameters $k, d, n$ are desirable?

\begin{enumerate}
  \item We'd like graphs that are sparse but have good expansion, so $d = O(1)$ is a desirable setting.
 \item Clearly $\gamma\leq d$, and a good setting for many applications (such as existence of good codes) is $\gamma >d/2$. Today  we'll show existence of expanders with $\gamma=d-2$. If $\gamma=(1-\eps)d$ for small $\eps$ the expander is called \emph{lossless}

  \item We want $K$ to be large, so $K =\alpha n$, for some $\alpha>0$.
\end{enumerate}

To see what can be achieved we state (but do not prove) the following settings that can be achieved.

\begin{theorem}
For all constants $d \geq 3$, $\exists$ a constant $\alpha > 0$ such that $\forall n$ large enough, a random $d$-regular  graph on $n$ vertices is an $(\alpha n, d - 1.01)$ vertex expander with probability at least $\frac{1}{2}$.
\end{theorem}
% \begin{proof}
% The goal is to get as close to $d$ as possible. $d \geq 3$ is best possible because for $d = 2$, every graph is a poor expander as we can have only cycles and lines. Also, for most settings of parameters, it is impossible to have an expansion larger than $d - 1$.
% \end{proof}

We next show the following slightly weaker(in terms of expansion) setting.
\begin{theorem}
For every constant $d$, $\exists$ a constant $\alpha > 0$ such that $\forall n$ large enough, a uniformly random graph $d$-left regular bipartite graph with $|L|=|R|=n$ is an $(\alpha n, d - 2)$ vertex expander with probability at least $\frac{1}{2}$.
\end{theorem}
\begin{proof}

 We use the probabilistic method. Pick a random $d$-left regular graph on $n\times n$ vertices by connecting each vertex on the left with $d$ vertices on the right with replacement. 

We will next compute the probability that the graph is not an expander.

For $k\leq \alpha n$ let $p_k = Pr[\exists S\subset L: |S| = k,\ |N(S)|\ <(d - 2)\cdot|S|]$.
 
Fix $S$ with $|S|=k$. So $N(S)$ is a set of random vertices $v_1, \ldots, v_{kd}$ (with possible repeats). We want to compute the probability that $S$ does not expand, namely $\Pr[|N(S)|<(d-2)k]=\Pr[\text{ there are at least } 2k \text{ repeated vertices among } v_1,\ldots, v_{kd}]$. 


For a fixed $v_i$, $\Pr[ v_i \text{ is a repeat }]\leq \frac{kd}{n}$. For a fixed $2k$ tuple $v_{i_1}, \ldots, v_{i_{2k}}$, $\Pr[ v_{i_1}, \ldots, v_{i_{2k}} \text{ are repeats }]\leq ({\frac{kd}{n}})^{2k}$. By a union bound  over all $2k$ tuples, $\Pr[|N(S)|< (d-2)|S|]=\Pr[\exists 2k \text{ repeats }]\leq {{kd}\choose{2k}}({\frac{kd}{n}})^{2k}.$ By another union bound over all sets $S$ of size $k$, 

$$Pr[\exists S, |S|=k: |N(S)|<(d - 2)|S|] \leq \binom{n}{k}\binom{kd}{2k}(\frac{kd}{n})^{2k}.$$
 
Using the approximation  $\binom{n}{k} \leq (\frac{ne}{k})^{k}$ (where $e$ is the base of the natural logarithm) the above expression can be bounded by $\leq (\frac{ne}{k})^{k}(\frac{dke}{2k})^{2k}(\frac{kd}{n})^{2k}\leq (\frac{e^3d^4k}{4n})^{k}$.
 Let $\alpha = \frac{1}{e^3d^4}$ and so $p_k \leq 4^{-k}$. Thus, again by a union bound $$\Pr[G \text{ is not } (\alpha n, d - 2)- expander] \leq \sum_{k=1}^{\alpha n}p_k\leq \sum_{k=1}^{\alpha n} 4^{-k} < \frac{1}{2}.$$ And so $\Pr[G \text{ is an }(\alpha n, d-2) \text{ expander }]>1/2$. (This says that half of the bipartite graphs chosen as above are expanders). 
 
\end{proof}



\section {Explicit Constructions}
While the existence of good expanders can be shown relatively easily, explicit expanders with good parameters (eg, $d$-regular graphs with $\gamma>1/2$) are hard to construct. These settings are useful in applications of networks that implement routing algorithms, data structures storage schemes, computational complexity applications (such as in constructing objects useful in the study of pseudorandomness  such as conductors, extractors and dispersers). 
The first explicit construction was algebraic.

\paragraph{(Margulis' Construction):} He constructed a $8$-regular expanders
   on the $\mathbb Z_n\times\mathbb Z_n$. For each $(x, y) \in V$, connect it to:
\newline
\begin{itemize}
  \item $T_1 = (x + 2y, y)$
  \item $T_2 = (x, 2x + y)$
  \item $T_3 = (x + 2y + 1, y)$
  \item $T_4 = (x, 2x + y + 1)$
  and to the inverses of these transformations.
\end{itemize}
%   The Linear transformation using the above expander would be:
%  \begin{itemize}
%   \item $T_1 = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}$
%   \item $T_2 = \begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix}$
%   \item $T_3 = \begin{pmatrix} 1  \\ 0  \end{pmatrix}$
%   \item $T_4 = \begin{pmatrix} 0 \\  1 \end{pmatrix}$
% \end{itemize}

Other algebraic examples:
\begin{enumerate} 
\item A $5$-regular expanders on $\mathbb Z_n \times \mathbb Z_n$. For each $(x, y) \in V$, connect it to:
\begin{itemize}
  \item $T_1 = (x, y)$
  \item $T_2 = (x+1, y)$
  \item $T_3 = (x, y+1)$
  \item $T_4 = (-y, x)$
  \item $T_5= (x, x+y)$.
\end{itemize}
  \item A $3$-regular expander on  $\mathbb Z_p$. For each $x \in V$, connect it to:
\newline
\begin{itemize}
  \item $T_1 = (x, x+1)$
  \item $T_2 = (x, x - 1)$
  \item $T_3 = (x, x^{-1})$
($0^{-1}=0$).
\end{itemize}
\end{enumerate}

More generally, \cite{CRVW} propose an explicit construction based on graph operations such as tensoring and the zig-zag product to construct, 
for any $\delta>0$ and sufficiently large $d$, an  $d$-left regular bipartite graph that is a $(\alpha n, (1-\delta)d)$-expander. 



\bibliographystyle{plain}
\bibliography{biblio}
\end{document}





